package algorithm.dynamicProgramming.leetcode;
//152. 乘积最大子数组
public class MaxProduct {

    public static void main(String[] args) {
        int[] data = {2,3,-2,4};
        System.out.println(maxProduct2(data));

    }
    //暴力
    public static int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int i=0;i<nums.length;i++){
            int res = 1;
            for (int j=i;j<nums.length;j++){
                res = res*nums[j];
                if (res>max){
                    max = res;
                }
            }
        }
        return max;
    }

    //动态规划
    public static int maxProduct2(int[] nums) {
//        当 j = 0 的时候，表示计算的是最小值；
//        当 j = 1 的时候，表示计算的是最大值。
        int[][] f = new int[nums.length][2];
        f[0][0]=f[0][1]=nums[0];
        for (int  i=1;i<nums.length;i++){
            if (nums[i]>=0){
                f[i][0]=Math.min(nums[i],f[i-1][0]*nums[i]);
                f[i][1]=Math.max(nums[i],f[i-1][1]*nums[i]);
            }else {
                f[i][0]=Math.min(nums[i],f[i-1][1]*nums[i]);
                f[i][1]=Math.max(nums[i],f[i-1][0]*nums[i]);
            }
        }
        int res = f[0][1];
        for (int i=1;i<nums.length;i++){
            res = Math.max(f[i][1], res);
        }
        return res;

    }
}
